1762G - Unequal Adjacent Elements - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
int _,n,a[1<<20],s[1<<20],c[1<<20],u,A[1<<20];
void O(){
	cin>>n,u=0;
	for(int i=1;i<=n;i++)
		s[i]=c[i]=0;
	for(int i=1;i<=n;i++)
		cin>>a[i],s[++c[a[i]]]++,u=max(u,c[a[i]]);
	if(u>(n+1)/2){
		cout<<"NO\n";
		return;
	}
	cout<<"YES\n";
	for(int i=1,l=1,r=2;i<=n;i++){
		if(u==(n-l+2)/2)
			for(int j=1;j<=n;j++)
				if(c[j]==u){
					for(int k=i;k<=n;k++)
						if(a[k]==j)
							A[l]=k,l+=2;
						else
							A[r]=k,r+=2;
					for(int k=1;k<=n;k++)
						cout<<A[k]<<" \n"[k==n];
					return;
				}
		if(a[i]!=a[A[l-1]]){
			A[l]=i,l+=2;
			if(l>r)
				swap(l,r);
		}else
			A[r]=i,r+=2;
		s[c[a[i]]--]--,u-=!s[u];
	}
}
int main(){
	for(cin>>_;_--;)
		O();
}